package Exercise;

import java.math.BigInteger;

public class AiWrite {
    public static int solution(int n, int k) {
        // write code here
//        long molecule=k-1;
//        long denominator=k+1;
//
//        long sum1=1;
//        long sum2=1;
//        while(n!=0){
//            long i=1;
//            sum1*=molecule;
//            sum2*=denominator;
//            long a=sum1;
//            long b=sum2;
//            while(i!=0){
//                i=a%b;
//                a=b;
//                b=i;
//            }
//            sum1/=a;
//            sum2/=a;
//            n--;
//        }
//        molecule=sum1;
//        denominator=sum2;
//        if(molecule%2==0){
//            molecule/=2;
//        }else{
//            denominator*=2;
//        }
//        if(denominator%2==0){
//            molecule+=(denominator/2);
//        }else{
//            molecule=molecule*2+denominator;
//            denominator*=2;
//        }
//        if(molecule==denominator){
//            return 1;
//        }else{
//            long i=1;
//            long a=molecule;
//            long b=denominator;
//            while(i!=0){
//                i=a%b;
//                a=b;
//                b=i;
//            }
//            molecule/=a;
//            denominator/=a;
//            return (int)(molecule+denominator)%10;
//        }
        BigInteger molecule = BigInteger.valueOf(k - 1);
        BigInteger denominator = BigInteger.valueOf(k + 1);

        BigInteger numeratorProduct = BigInteger.ONE;
        BigInteger denominatorProduct = BigInteger.ONE;

        while (n != 0) {
            numeratorProduct = numeratorProduct.multiply(molecule);
            denominatorProduct = denominatorProduct.multiply(denominator);

            // 计算最大公约数并化简
            BigInteger gcd = numeratorProduct.gcd(denominatorProduct);
            numeratorProduct = numeratorProduct.divide(gcd);
            denominatorProduct = denominatorProduct.divide(gcd);

            n--;
        }
        // 处理分数的化简
        if (numeratorProduct.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
            numeratorProduct = numeratorProduct.divide(BigInteger.valueOf(2));
        } else {
            denominatorProduct = denominatorProduct.multiply(BigInteger.valueOf(2));
        }

        if (denominatorProduct.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
            numeratorProduct = numeratorProduct.add(denominatorProduct.divide(BigInteger.valueOf(2)));
        } else {
            numeratorProduct = numeratorProduct.multiply(BigInteger.valueOf(2)).add(denominatorProduct);
            denominatorProduct = denominatorProduct.multiply(BigInteger.valueOf(2));
        }

        if (numeratorProduct.equals(denominatorProduct)) {
            return 1;
        } else {
            BigInteger gcd = numeratorProduct.gcd(denominatorProduct);
            numeratorProduct = numeratorProduct.divide(gcd);
            denominatorProduct = denominatorProduct.divide(gcd);
            return (numeratorProduct.add(denominatorProduct)).mod(BigInteger.TEN).intValue();
        }

    }

    public static void main(String[] args) {
        System.out.println(solution(2, 5) == 1);
        System.out.println(solution(2, 6) == 6);
        System.out.println(solution(3, 7) == 9);
        System.out.println(solution(3, 9) == 9);
        System.out.println(solution(13, 17) == 5);
    }
}
